{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #传送卷轴"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: challengeOfTheKeeper"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #传送卷轴"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "随着不断的深入，小扣来到了守护者之森寻找的魔法水晶。首先，他必须先通过守护者的考验。\n",
    "\n",
    "考验的区域是一个正方形的迷宫，`maze[i][j]` 表示在迷宫 `i` 行 `j` 列的地形：\n",
    "- 若为 `.` ，表示可以到达的空地；\n",
    "- 若为 `#` ，表示不可到达的墙壁；\n",
    "- 若为 `S` ，表示小扣的初始位置；\n",
    "- 若为 `T` ，表示魔法水晶的位置。\n",
    "\n",
    "小扣每次可以向 上、下、左、右 相邻的位置移动一格。而守护者拥有一份「传送魔法卷轴」，使用规则如下：\n",
    "- 魔法需要在小扣位于 **空地** 时才能释放，发动后卷轴消失；；\n",
    "- 发动后，小扣会被传送到水平或者竖直的镜像位置，且目标位置不得为墙壁(如下图所示)；\n",
    "![image.png](https://pic.leetcode.cn/1681789509-wTekFu-image.png){:width=400px}\n",
    "\n",
    "在使用卷轴后，小扣将被「附加负面效果」，因此小扣需要尽可能缩短传送后到达魔法水晶的距离。而守护者的目标是阻止小扣到达魔法水晶的位置；如果无法阻止，则尽可能 **增加** 小扣传送后到达魔法水晶的距离。\n",
    "假设小扣和守护者都按最优策略行事，返回小扣需要在 「附加负面效果」的情况下 **最少** 移动多少次才能到达魔法水晶。如果无法到达，返回 `-1`。\n",
    "\n",
    "**注意：**\n",
    "- 守护者可以不使用卷轴；\n",
    "- 传送后的镜像位置可能与原位置相同。\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`maze = [\".....\",\"##S..\",\"...#.\",\"T.#..\",\"###..\"]`\n",
    ">\n",
    ">输出：`7`\n",
    ">\n",
    ">解释：如下图所示：\n",
    ">守护者释放魔法的两个最佳的位置为 [2,0] 或 [3,1]：\n",
    ">若小扣经过 [2,0]，守护者在该位置释放魔法，\n",
    ">小扣被传送至 [2,4] 处且加上负面效果，此时小扣还需要移动 7 次才能到达魔法水晶；\n",
    ">若小扣经过 [3,1]，守护者在该位置释放魔法，\n",
    ">小扣被传送至 [3,3] 处且加上负面效果，此时小扣还需要移动 9 次才能到达魔法水晶；\n",
    ">因此小扣负面效果下最少需要移动 7 次才能到达魔法水晶。\n",
    "![image.png](https://pic.leetcode.cn/1681714676-gksEMT-image.png){:width=300px}\n",
    "\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`maze = [\".#..\",\"..##\",\".#S.\",\".#.T\"]`\n",
    ">\n",
    ">输出：`-1`\n",
    ">\n",
    ">解释：如下图所示。\n",
    ">若小扣向下移动至 [3,2]，守护者使其传送至 [0,2]，小扣将无法到达魔法水晶；\n",
    ">若小扣向右移动至 [2,3]，守护者使其传送至 [2,0]，小扣将无法到达魔法水晶；\n",
    "![image.png](https://pic.leetcode.cn/1681714693-LsxKAh-image.png){:width=300px}\n",
    "\n",
    "\n",
    "**示例 3：**\n",
    ">输入：`maze = [\"S###.\",\"..###\",\"#..##\",\"##..#\",\"###.T\"]`\n",
    ">\n",
    ">输出：`5`\n",
    ">\n",
    ">解释：如下图所示：\n",
    ">守护者需要小扣在空地才能释放，因此初始无法将其从 [0,0] 传送至 [0,4];\n",
    ">当小扣移动至 [2,1] 时，释放卷轴将其传送至水平方向的镜像位置 [2,1]（为原位置）\n",
    ">而后小扣需要移动 5 次到达魔法水晶\n",
    "![image.png](https://pic.leetcode.cn/1681800985-KrSdru-image.png){:width=300px}\n",
    "\n",
    "**提示：**\n",
    "- `4 <= maze.length == maze[i].length <= 200`\n",
    "- `maze[i][j]` 仅包含 `\".\"`、`\"#\"`、`\"S\"`、`\"T\"`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [rdmXM7](https://leetcode.cn/problems/rdmXM7/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [rdmXM7](https://leetcode.cn/problems/rdmXM7/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\".....\",\"##S..\",\"...#.\",\"T.#..\",\"###..\"]', '[\".#..\",\"..##\",\".#S.\",\".#.T\"]', '[\"S###.\",\"..###\",\"#..##\",\"##..#\",\"###.T\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def challengeOfTheKeeper(self, mz: List[str]) -> int:\n",
    "        m, n = len(mz), len(mz)\n",
    "        g = [[inf] * n for _ in range(m)]\n",
    "        for i, row in enumerate(mz):\n",
    "            for j, v in enumerate(row):\n",
    "                if v == 'S':\n",
    "                    sx, sy = i, j\n",
    "                elif v == 'T':\n",
    "                    tx, ty = i, j\n",
    "\n",
    "        g[tx][ty] = 0\n",
    "        q = [(tx, ty)]\n",
    "        stp = 1\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = list()\n",
    "            for i, j in tmp:\n",
    "                for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):\n",
    "                    if m > x >= 0 <= y < n and g[x][y] == inf and mz[x][y] != \"#\":\n",
    "                        g[x][y] = stp\n",
    "                        q.append((x, y))\n",
    "            stp += 1\n",
    "\n",
    "        if g[sx][sy] == inf: return -1\n",
    "\n",
    "        g1 = deepcopy(g)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mz[i][j] == \".\" and g[i][j] != inf:\n",
    "                    if mz[m - 1 - i][j] == '#' and mz[i][n - 1 - j] == '#':\n",
    "                        g[i][j] = 0\n",
    "                    elif mz[m - 1 - i][j] == '#':\n",
    "                        g[i][j] = g1[i][n - 1 - j]\n",
    "                    elif mz[i][n - 1 - j] == '#':\n",
    "                        g[i][j] = g1[m - 1 - i][j]\n",
    "                    else:\n",
    "                        g[i][j] = max(g1[m - 1 - i][j], g1[i][n - 1 - j])\n",
    "\n",
    "        g[sx][sy] = inf\n",
    "        h = list()\n",
    "        heappush(h, (0, sx, sy))\n",
    "        while h:\n",
    "            dis, i, j = heappop(h)\n",
    "            for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):\n",
    "                if m > x >= 0 <= y < n and g[x][y] != inf:\n",
    "                    if (x, y) == (tx, ty):\n",
    "                        return dis\n",
    "                    heappush(h, (max(g[x][y], dis), x, y))\n",
    "                    g[x][y] = inf\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @classmethod\n",
    "    def check(cls, sx, sy, tx, ty, v, maze, t_dis):\n",
    "        n = len(maze)\n",
    "        m = len(maze[0])\n",
    "        direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "\n",
    "        vis = [[False for j in range(m)] for i in range(n)]\n",
    "\n",
    "        queue = [(sx, sy)]\n",
    "        vis[sx][sy] = True\n",
    "        while len(queue):\n",
    "            tmpx, tmpy = queue.pop(0)\n",
    "            for d in range(4):\n",
    "                xx = tmpx + direction[d][0]\n",
    "                yy = tmpy + direction[d][1]\n",
    "                if xx == tx and yy == ty:\n",
    "                    return True\n",
    "                if xx >= 0 and xx < n and yy >= 0 and yy < m and vis[xx][yy] is False and maze[xx][yy] != '#' and (maze[n-1-xx][yy] == '#' or t_dis[n-1-xx][yy] <= v) and (maze[xx][m-1-yy] == '#' or t_dis[xx][m-1-yy] <= v):\n",
    "                    queue.append((xx, yy))\n",
    "                    vis[xx][yy] = True\n",
    "        return False\n",
    "\n",
    "\n",
    "    def challengeOfTheKeeper(self, maze: List[str]) -> int:\n",
    "        n = len(maze)\n",
    "        m = len(maze[0])\n",
    "\n",
    "        direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        t_dis = [[1000000 for j in range(m)] for i in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if maze[i][j] == 'S':\n",
    "                    sx = i\n",
    "                    sy = j\n",
    "                if maze[i][j] == 'T':\n",
    "                    tx = i\n",
    "                    ty = j\n",
    "        \n",
    "        queue = [(tx, ty)]\n",
    "        t_dis[tx][ty] = 0\n",
    "        while len(queue):\n",
    "            tmpx, tmpy = queue.pop(0)\n",
    "            for d in range(4):\n",
    "                xx = tmpx + direction[d][0]\n",
    "                yy = tmpy + direction[d][1]\n",
    "                if xx >= 0 and xx < n and yy >= 0 and yy < m and maze[xx][yy] != '#' and t_dis[xx][yy] > t_dis[tmpx][tmpy] + 1:\n",
    "                    t_dis[xx][yy] = t_dis[tmpx][tmpy] + 1\n",
    "                    queue.append((xx, yy))\n",
    "        \n",
    "        l = 0\n",
    "        r = 100000\n",
    "        ans = 100000\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if Solution.check(sx, sy, tx, ty, mid, maze, t_dis) is True:\n",
    "                ans = min(ans, mid)\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "\n",
    "        if ans == 100000:\n",
    "            return -1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def challengeOfTheKeeper(self, maze: List[str]) -> int:\n",
    "      n = len(maze)\n",
    "      INF = 1e9\n",
    "      d = [[INF for _ in range(n)] for _ in range(n)]\n",
    "      Q = deque()\n",
    "      edx, edy = -1, -1\n",
    "      for i in range(n):\n",
    "        for j in range(n):\n",
    "          if maze[i][j] == 'T':\n",
    "            Q.append((i, j))\n",
    "            d[i][j] = 0\n",
    "            edx, edy = i, j\n",
    "            break\n",
    "      dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "      while Q:\n",
    "        x, y = Q.popleft()\n",
    "        for dx, dy in dirs:\n",
    "          nx, ny = x + dx, y + dy\n",
    "          if min(nx, ny) < 0 or max(nx, ny) >= n or maze[nx][ny] == '#' or d[nx][ny] <= d[x][y] + 1:\n",
    "            continue\n",
    "          d[nx][ny] = d[x][y] + 1\n",
    "          Q.append((nx, ny))\n",
    "      \n",
    "      def cost(i, j):\n",
    "        ret = 0\n",
    "        if maze[i][j] == 'S' or maze[i][j] == 'T':\n",
    "          return 0\n",
    "        if maze[n - 1 - i][j] != '#':\n",
    "          ret = max(ret, d[n - 1 - i][j])\n",
    "        if maze[i][n - 1 - j] != '#':\n",
    "          ret = max(ret, d[i][n - 1 - j])\n",
    "        return ret\n",
    "      \n",
    "      Q = []\n",
    "      d2 = [[INF for _ in range(n)] for _ in range(n)]\n",
    "      for i in range(n):\n",
    "        for j in range(n):\n",
    "          if maze[i][j] == 'S':\n",
    "            Q.append((0, i, j))\n",
    "            d2[i][j] = 0\n",
    "            break\n",
    "      heapify(Q)\n",
    "      while Q:\n",
    "        c, x, y = heappop(Q)\n",
    "        if c > d2[x][y]:\n",
    "          continue\n",
    "        for dx, dy in dirs:\n",
    "          nx, ny = x + dx, y + dy\n",
    "          if min(nx, ny) < 0 or max(nx, ny) >= n or maze[nx][ny] == '#':\n",
    "            continue\n",
    "          c2 = max(c, cost(nx, ny))\n",
    "          if d2[nx][ny] > c2:\n",
    "            d2[nx][ny] = c2\n",
    "            heappush(Q, (c2, nx, ny))\n",
    "            \n",
    "      return -1 if d2[edx][edy] == INF else d2[edx][edy]\n",
    "            \n",
    "          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def challengeOfTheKeeper(self, maze: List[str]) -> int:\n",
    "      n = len(maze)\n",
    "      d = [[inf for _ in range(n)] for _ in range(n)]\n",
    "      Q = deque()\n",
    "      for i in range(n):\n",
    "        for j in range(n):\n",
    "          if maze[i][j] == 'T':\n",
    "            Q.append((i, j))\n",
    "            d[i][j] = 0\n",
    "            tx, ty = i, j\n",
    "          elif maze[i][j] == 'S':\n",
    "            sx, sy = i, j\n",
    "\n",
    "      while Q:\n",
    "        x, y = Q.popleft()\n",
    "        for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "          if min(nx, ny) < 0 or max(nx, ny) >= n or maze[nx][ny] == '#' or d[nx][ny] <= d[x][y] + 1:\n",
    "            continue\n",
    "          d[nx][ny] = d[x][y] + 1\n",
    "          Q.append((nx, ny))\n",
    "      \n",
    "      if d[sx][sy] == inf:\n",
    "        return -1\n",
    "      \n",
    "      def cost(i, j):\n",
    "        ret = 0\n",
    "        if maze[i][j] == 'S' or maze[i][j] == 'T':\n",
    "          return 0\n",
    "        if maze[n - 1 - i][j] != '#':\n",
    "          ret = max(ret, d[n - 1 - i][j])\n",
    "        if maze[i][n - 1 - j] != '#':\n",
    "          ret = max(ret, d[i][n - 1 - j])\n",
    "        return ret\n",
    "      \n",
    "      Q = []\n",
    "      d2 = [[inf for _ in range(n)] for _ in range(n)]\n",
    "      C = [[cost(i, j) for j in range(n)] for i in range(n)]\n",
    "      \n",
    "      heappush(Q, (0, sx, sy))\n",
    "      d2[sx][sy] = 0\n",
    "      while Q:\n",
    "        c, x, y = heappop(Q)\n",
    "        if c > d2[x][y]:\n",
    "          continue\n",
    "        for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "          if min(nx, ny) < 0 or max(nx, ny) >= n or maze[nx][ny] == '#':\n",
    "            continue\n",
    "          if (nx, ny) == (tx, ty):\n",
    "            return c\n",
    "          c2 = max(c, C[nx][ny])\n",
    "          if d2[nx][ny] > c2:\n",
    "            d2[nx][ny] = c2\n",
    "            heappush(Q, (c2, nx, ny))\n",
    "            \n",
    "      return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def challengeOfTheKeeper(self, maze: List[str]) -> int:\n",
    "      n = len(maze)\n",
    "      d = [[inf for _ in range(n)] for _ in range(n)]\n",
    "      Q = deque()\n",
    "      for i in range(n):\n",
    "        for j in range(n):\n",
    "          if maze[i][j] == 'T':\n",
    "            Q.append((i, j))\n",
    "            d[i][j] = 0\n",
    "            tx, ty = i, j\n",
    "          elif maze[i][j] == 'S':\n",
    "            sx, sy = i, j\n",
    "\n",
    "      while Q:\n",
    "        x, y = Q.popleft()\n",
    "        for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "          if min(nx, ny) < 0 or max(nx, ny) >= n or maze[nx][ny] == '#' or d[nx][ny] <= d[x][y] + 1:\n",
    "            continue\n",
    "          d[nx][ny] = d[x][y] + 1\n",
    "          Q.append((nx, ny))\n",
    "      \n",
    "      if d[sx][sy] == inf:\n",
    "        return -1\n",
    "      \n",
    "      Q = []\n",
    "      d2 = [[inf for _ in range(n)] for _ in range(n)]\n",
    "      C = [[0 for _ in range(n)] for _ in range(n)]\n",
    "      for i in range(n):\n",
    "        for j in range(n):\n",
    "          if maze[i][j] == '.':\n",
    "            if maze[n - 1 - i][j] != '#':\n",
    "              C[i][j] = max(C[i][j], d[n - 1 - i][j])\n",
    "            if maze[i][n - 1 - j] != '#':\n",
    "              C[i][j] = max(C[i][j], d[i][n - 1 - j])\n",
    "      \n",
    "      heappush(Q, (0, sx, sy))\n",
    "      d2[sx][sy] = 0\n",
    "      while Q:\n",
    "        c, x, y = heappop(Q)\n",
    "        if c > d2[x][y]:\n",
    "          continue\n",
    "        for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "          if min(nx, ny) < 0 or max(nx, ny) >= n or maze[nx][ny] == '#':\n",
    "            continue\n",
    "          if (nx, ny) == (tx, ty):\n",
    "            return c\n",
    "          c2 = max(c, C[nx][ny])\n",
    "          if d2[nx][ny] > c2:\n",
    "            d2[nx][ny] = c2\n",
    "            heappush(Q, (c2, nx, ny))\n",
    "\n",
    "      return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def challengeOfTheKeeper(self, maze: List[str]) -> int:\n",
    "      n = len(maze)\n",
    "      d = [[inf for _ in range(n)] for _ in range(n)]\n",
    "      Q = deque()\n",
    "      for i in range(n):\n",
    "        for j in range(n):\n",
    "          if maze[i][j] == 'T':\n",
    "            Q.append((i, j))\n",
    "            d[i][j] = 0\n",
    "            tx, ty = i, j\n",
    "          elif maze[i][j] == 'S':\n",
    "            sx, sy = i, j\n",
    "\n",
    "      while Q:\n",
    "        x, y = Q.popleft()\n",
    "        for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):\n",
    "          if min(nx, ny) < 0 or max(nx, ny) >= n or maze[nx][ny] == '#' or d[nx][ny] <= d[x][y] + 1:\n",
    "            continue\n",
    "          d[nx][ny] = d[x][y] + 1\n",
    "          Q.append((nx, ny))\n",
    "      \n",
    "      if d[sx][sy] == inf:\n",
    "        return -1\n",
    "      \n",
    "      Q = []\n",
    "      d2 = [[inf for _ in range(n)] for _ in range(n)]\n",
    "      C = [[0 for _ in range(n)] for _ in range(n)]\n",
    "      for i in range(n):\n",
    "        for j in range(n):\n",
    "          if maze[i][j] == '.':\n",
    "            if maze[n - 1 - i][j] != '#':\n",
    "              C[i][j] = max(C[i][j], d[n - 1 - i][j])\n",
    "            if maze[i][n - 1 - j] != '#':\n",
    "              C[i][j] = max(C[i][j], d[i][n - 1 - j])\n",
    "      \n",
    "      heappush(Q, (0, sx, sy))\n",
    "      d2[sx][sy] = 0\n",
    "      while Q:\n",
    "        c, x, y = heappop(Q)\n",
    "        if c > d2[x][y]:\n",
    "          continue\n",
    "        for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):\n",
    "          if min(nx, ny) < 0 or max(nx, ny) >= n or maze[nx][ny] == '#':\n",
    "            continue\n",
    "          if (nx, ny) == (tx, ty):\n",
    "            return c\n",
    "          c2 = max(c, C[nx][ny])\n",
    "          if d2[nx][ny] > c2:\n",
    "            d2[nx][ny] = c2\n",
    "            heappush(Q, (c2, nx, ny))\n",
    "\n",
    "      return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def challengeOfTheKeeper(self, maze: List[str]) -> int:\n",
    "        # . ，表示可以到达的空地；\n",
    "        # # ，表示不可到达的墙壁；\n",
    "        # S ，表示小扣的初始位置；\n",
    "        # T ，表示魔法水晶的位置。\n",
    "        M, N = len(maze), len(maze[0])\n",
    "\n",
    "        # 达到T的位置\n",
    "        jls = [[-1] * N for _ in range(M)]\n",
    "        dp = []\n",
    "        fxs = ((0, 1), (0, -1), (1, 0), (-1, 0))\n",
    "\n",
    "        for m, row in enumerate(maze):\n",
    "            for n, v in enumerate(row):\n",
    "                if v == \"T\":\n",
    "                    dp = [(m, n)]\n",
    "                    jls[m][n] = 0\n",
    "                    tm, tn = m, n\n",
    "                elif v == \"#\":\n",
    "                    jls[m][n] = -2\n",
    "                elif v == \"S\":\n",
    "                    sm, sn = m, n\n",
    "\n",
    "        while dp:\n",
    "            _m, _n = dp.pop(0)\n",
    "            jl = jls[_m][_n] + 1\n",
    "\n",
    "            for om, on in fxs:\n",
    "                m = _m + om\n",
    "                if m < 0 or m == M:\n",
    "                    continue\n",
    "\n",
    "                n = _n + on\n",
    "                if n < 0 or n == N:\n",
    "                    continue\n",
    "\n",
    "                if jls[m][n] == -2:\n",
    "                    continue\n",
    "\n",
    "                if jls[m][n] == -1:\n",
    "                    jls[m][n] = jl\n",
    "                    dp.append((m, n))\n",
    "\n",
    "        if jls[sm][sn] == -1:\n",
    "            return -1\n",
    "\n",
    "        if jls[sm][sn] == 1:\n",
    "            return 0\n",
    "\n",
    "        # 每个位置对应的镜像位置的最大距离值\n",
    "        jxjls = [[-1] * N for _ in range(M)]\n",
    "\n",
    "        for m, row in enumerate(jls):\n",
    "            for n, jl in enumerate(row):\n",
    "                if jl < 0:\n",
    "                    continue\n",
    "\n",
    "                # 水平镜像\n",
    "                jl1 = jls[M - 1 - m][n]\n",
    "\n",
    "                # 竖直镜像\n",
    "                jl2 = jls[m][N - 1 - n]\n",
    "\n",
    "                if jl1 == -1 or jl2 == -1:\n",
    "                    continue\n",
    "\n",
    "                if jl1 == -2:\n",
    "                    jxjls[m][n] = jl2\n",
    "                elif jl2 == -1:\n",
    "                    jxjls[m][n] = jl1\n",
    "                else:\n",
    "                    jxjls[m][n] = max(jl1, jl2)\n",
    "\n",
    "        # ST设置为1\n",
    "        jxjls[tm][tn] = jxjls[sm][sn] = 0\n",
    "\n",
    "        # ppp(jls)\n",
    "        # ppp(jxjls)\n",
    "\n",
    "        # 每个点到T的每条路径，取路径上最大的jxjl值，返回所有路径中该值得最小值\n",
    "        jls = [[-1] * N for _ in range(M)]\n",
    "        jls[tm][tn] = 0\n",
    "\n",
    "        dp = [(tm, tn)]\n",
    "\n",
    "        while dp:\n",
    "            _m, _n = dp.pop(0)\n",
    "            _jl = jls[_m][_n]\n",
    "\n",
    "            for om, on in fxs:\n",
    "                m = _m + om\n",
    "                if m < 0 or m == M:\n",
    "                    continue\n",
    "\n",
    "                n = _n + on\n",
    "                if n < 0 or n == N:\n",
    "                    continue\n",
    "\n",
    "                if jxjls[m][n] == -1:\n",
    "                    continue\n",
    "\n",
    "                jl = max(_jl, jxjls[m][n])\n",
    "                if jls[m][n] == -1 or jls[m][n] > jl:\n",
    "                    jls[m][n] = jl\n",
    "                    dp.append((m, n))\n",
    "\n",
    "        return jls[sm][sn]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def challengeOfTheKeeper(self, maze: List[str]) -> int:\n",
    "      n = len(maze)\n",
    "      INF = 1e9\n",
    "      d = [[INF for _ in range(n)] for _ in range(n)]\n",
    "      Q = deque()\n",
    "      edx, edy = -1, -1\n",
    "      for i in range(n):\n",
    "        for j in range(n):\n",
    "          if maze[i][j] == 'T':\n",
    "            Q.append((i, j))\n",
    "            d[i][j] = 0\n",
    "            edx, edy = i, j\n",
    "            break\n",
    "      dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "      while Q:\n",
    "        x, y = Q.popleft()\n",
    "        for dx, dy in dirs:\n",
    "          nx, ny = x + dx, y + dy\n",
    "          if min(nx, ny) < 0 or max(nx, ny) >= n or maze[nx][ny] == '#' or d[nx][ny] <= d[x][y] + 1:\n",
    "            continue\n",
    "          d[nx][ny] = d[x][y] + 1\n",
    "          Q.append((nx, ny))\n",
    "      \n",
    "      def cost(i, j):\n",
    "        ret = 0\n",
    "        if maze[i][j] == 'S' or maze[i][j] == 'T':\n",
    "          return 0\n",
    "        if maze[n - 1 - i][j] != '#':\n",
    "          ret = max(ret, d[n - 1 - i][j])\n",
    "        if maze[i][n - 1 - j] != '#':\n",
    "          ret = max(ret, d[i][n - 1 - j])\n",
    "        return ret\n",
    "      \n",
    "      Q = []\n",
    "      d2 = [[INF for _ in range(n)] for _ in range(n)]\n",
    "      C = [[cost(i, j) for j in range(n)] for i in range(n)]\n",
    "      for i in range(n):\n",
    "        for j in range(n):\n",
    "          if maze[i][j] == 'S':\n",
    "            Q.append((0, i, j))\n",
    "            d2[i][j] = 0\n",
    "            break\n",
    "      heapify(Q)\n",
    "      while Q:\n",
    "        c, x, y = heappop(Q)\n",
    "        if c > d2[x][y]:\n",
    "          continue\n",
    "        for dx, dy in dirs:\n",
    "          nx, ny = x + dx, y + dy\n",
    "          if min(nx, ny) < 0 or max(nx, ny) >= n or maze[nx][ny] == '#':\n",
    "            continue\n",
    "          c2 = max(c, C[nx][ny])\n",
    "          if d2[nx][ny] > c2:\n",
    "            d2[nx][ny] = c2\n",
    "            heappush(Q, (c2, nx, ny))\n",
    "            \n",
    "      return -1 if d2[edx][edy] == INF else d2[edx][edy]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def challengeOfTheKeeper(self, maze: List[str]) -> int:\n",
    "        m, n = len(maze), len(maze[0])\n",
    "\n",
    "        # 1. 找到起点终点坐标\n",
    "        for i, row in enumerate(maze):\n",
    "            for j, c in enumerate(row):\n",
    "                if c == 'S':\n",
    "                    sx, sy = i, j\n",
    "                elif c == 'T':\n",
    "                    tx, ty = i, j\n",
    "\n",
    "        # 2. BFS 计算终点到其余点的最短距离\n",
    "        dis_from_t = [[inf] * n for _ in range(m)]\n",
    "        dis_from_t[tx][ty] = 0\n",
    "        q = [(tx, ty)]\n",
    "        step = 1\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j in tmp:\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n and maze[x][y] != '#' and dis_from_t[x][y] == inf:\n",
    "                        dis_from_t[x][y] = step\n",
    "                        q.append((x, y))\n",
    "            step += 1\n",
    "\n",
    "        # 3. 剪枝：如果 S 无法到达 T，直接返回 -1\n",
    "        if dis_from_t[sx][sy] == inf:\n",
    "            return -1\n",
    "\n",
    "        # 4. 二分答案 https://www.bilibili.com/video/BV1AP41137w7/\n",
    "        vis = [[-1] * n for _ in range(m)]\n",
    "        def check(max_dis: int) -> bool:\n",
    "            # DFS，看能否在「附加负面效果」的情况下，移动不超过 max_dis 步到达终点\n",
    "            def dfs(i: int, j: int) -> bool:\n",
    "                if i < 0 or i >= m or j < 0 or j >= n or vis[i][j] == max_dis or maze[i][j] == '#':\n",
    "                    return False\n",
    "                if maze[i][j] == 'T':  # 到达终点\n",
    "                    return True\n",
    "                vis[i][j] = max_dis  # 为避免反复创建 vis，用一个每次二分都不一样的数来标记\n",
    "                # 守护者使用卷轴传送小扣，如果小扣无法在 maxDis 步内到达终点，则返回 false\n",
    "                if maze[i][j] == '.' and (maze[i][n - 1 - j] != '#' and dis_from_t[i][n - 1 - j] > max_dis or\n",
    "                    maze[m - 1 - i][j] != '#' and dis_from_t[m - 1 - i][j] > max_dis):\n",
    "                    return False\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if dfs(x, y):\n",
    "                        return True\n",
    "                return False\n",
    "            return dfs(sx, sy)\n",
    "        ans = bisect_left(range(m * n + 1), True, key=check)\n",
    "        return -1 if ans > m * n else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def challengeOfTheKeeper(self, maze: List[str]) -> int:\n",
    "        m, n = len(maze), len(maze[0])\n",
    "\n",
    "        # 1. 找到起点终点坐标\n",
    "        for i, row in enumerate(maze):\n",
    "            for j, c in enumerate(row):\n",
    "                if c == 'S':\n",
    "                    sx, sy = i, j\n",
    "                elif c == 'T':\n",
    "                    tx, ty = i, j\n",
    "\n",
    "        # 2. BFS 计算终点到其余点的最短距离\n",
    "        dis_from_t = [[inf] * n for _ in range(m)]\n",
    "        dis_from_t[tx][ty] = 0\n",
    "        q = [(tx, ty)]\n",
    "        step = 1\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j in tmp:\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n and maze[x][y] != '#' and dis_from_t[x][y] == inf:\n",
    "                        dis_from_t[x][y] = step\n",
    "                        q.append((x, y))\n",
    "            step += 1\n",
    "\n",
    "        # 3. 剪枝：如果 S 无法到达 T，直接返回 -1\n",
    "        if dis_from_t[sx][sy] == inf:\n",
    "            return -1\n",
    "\n",
    "        # 4. 二分答案 https://www.bilibili.com/video/BV1AP41137w7/\n",
    "        vis = [[-1] * n for _ in range(m)]\n",
    "        def check(max_dis: int) -> bool:\n",
    "            # DFS，看能否在「附加负面效果」的情况下，移动不超过 max_dis 步到达终点\n",
    "            def dfs(i: int, j: int) -> bool:\n",
    "                if i < 0 or i >= m or j < 0 or j >= n or vis[i][j] == max_dis or maze[i][j] == '#':\n",
    "                    return False\n",
    "                if maze[i][j] == 'T':  # 到达终点\n",
    "                    return True\n",
    "                vis[i][j] = max_dis  # 为避免反复创建 vis，用一个每次二分都不一样的数来标记\n",
    "                # 守护者使用卷轴传送小扣，如果小扣无法在 maxDis 步内到达终点，则返回 false\n",
    "                if maze[i][j] == '.' and \\\n",
    "                   (maze[i][n - 1 - j] != '#' and dis_from_t[i][n - 1 - j] > max_dis or\n",
    "                    maze[m - 1 - i][j] != '#' and dis_from_t[m - 1 - i][j] > max_dis):\n",
    "                    return False\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if dfs(x, y):\n",
    "                        return True\n",
    "                return False\n",
    "            return dfs(sx, sy)\n",
    "        ans = bisect_left(range(m * n + 1), True, key=check)\n",
    "        return -1 if ans > m * n else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left\n",
    "from math import inf\n",
    "\n",
    "class Solution:\n",
    "    def challengeOfTheKeeper(self, maze: List[str]) -> int:\n",
    "        m, n = len(maze), len(maze[0])\n",
    "\n",
    "        # 1. 找到起点和终点的坐标\n",
    "        for i, row in enumerate(maze):\n",
    "            for j, c in enumerate(row):\n",
    "                if c == 'S':\n",
    "                    sx, sy = i, j\n",
    "                elif c == 'T':\n",
    "                    tx, ty = i, j\n",
    "\n",
    "        # 2. BFS 计算终点到其余点的最短距离\n",
    "        dis_from_t = [[inf] * n for _ in range(m)]\n",
    "        dis_from_t[tx][ty] = 0\n",
    "        q = [(tx, ty)]\n",
    "        step = 1\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j in tmp:\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if 0 <= x < m and 0 <= y < n and maze[x][y] != '#' and dis_from_t[x][y] == inf:\n",
    "                        dis_from_t[x][y] = step\n",
    "                        q.append((x, y))\n",
    "            step += 1\n",
    "\n",
    "        # 3. 判断 S 是否可以到达 T\n",
    "        if dis_from_t[sx][sy] == inf:\n",
    "            return -1\n",
    "\n",
    "        # 4. 二分查找\n",
    "        vis = [[-1] * n for _ in range(m)]\n",
    "        def check(max_dis: int) -> bool:\n",
    "            def dfs(i: int, j: int) -> bool:\n",
    "                if i < 0 or i >= m or j < 0 or j >= n or vis[i][j] == max_dis or maze[i][j] == '#':\n",
    "                    return False\n",
    "                if maze[i][j] == 'T':\n",
    "                    return True\n",
    "                vis[i][j] = max_dis\n",
    "                if maze[i][j] == '.' and \\\n",
    "                   (maze[i][n - 1 - j] != '#' and dis_from_t[i][n - 1 - j] > max_dis or\n",
    "                    maze[m - 1 - i][j] != '#' and dis_from_t[m - 1 - i][j] > max_dis):\n",
    "                    return False\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    if dfs(x, y):\n",
    "                        return True\n",
    "                return False\n",
    "            return dfs(sx, sy)\n",
    "        \n",
    "        ans = bisect_left(range(m * n + 1), True, key=check)\n",
    "        return -1 if ans > m * n else ans\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
